{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Duplicate Zeros"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: duplicateZeros"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #复写零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度固定的整数数组&nbsp;<code>arr</code> ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。</p>\n",
    "\n",
    "<p>注意：请不要在超过该数组长度的位置写入元素。请对输入的数组&nbsp;<strong>就地&nbsp;</strong>进行上述修改，不要从函数返回任何东西。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,0,2,3,0,4,5,0]\n",
    "<strong>输出：</strong>[1,0,0,2,3,0,0,4]\n",
    "<strong>解释：</strong>调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3]\n",
    "<strong>输出：</strong>[1,2,3]\n",
    "<strong>解释：</strong>调用函数后，输入的数组将被修改为：[1,2,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [duplicate-zeros](https://leetcode.cn/problems/duplicate-zeros/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [duplicate-zeros](https://leetcode.cn/problems/duplicate-zeros/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,2,3,0,4,5,0]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, A: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        if not A: return \n",
    "        def shift(A,i):\n",
    "            for j in range(len(A)-1,i,-1):\n",
    "                A[j] = A[j-1]\n",
    "                \n",
    "        i=0\n",
    "        while i < len(A):\n",
    "            if A[i]==0:\n",
    "                shift(A,i)\n",
    "                i+=2\n",
    "            else:\n",
    "                i+=1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        if len(arr) >= 2:\n",
    "            i = 0\n",
    "            length = len(arr)\n",
    "            while i <= length - 1:\n",
    "                if arr[i] == 0:\n",
    "                    arr.insert(i+1, 0)\n",
    "                    arr.pop()\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "                    \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        idx = 0\n",
    "        while idx < len(arr) - 1:\n",
    "            if arr[idx] == 0 :\n",
    "                for i in range(len(arr) -2, idx, -1):\n",
    "                    arr[i + 1] = arr[i]\n",
    "                arr[idx + 1] = 0\n",
    "                idx += 1\n",
    "            idx += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        if  0  not  in arr:\n",
    "            print(arr)\n",
    "            return arr\n",
    "        l = len(arr)\n",
    "        j = -1\n",
    "        for i in range(1,l):\n",
    "            if  arr[i-1] == 0  and  j!=i:\n",
    "               arr.insert(i,0)\n",
    "               j = i+1\n",
    "        while    len(arr)  -l:\n",
    "            arr.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        count = 0\n",
    "        while count < len(arr):\n",
    "            if arr[count] == 0:\n",
    "                arr.insert(count,0)\n",
    "                arr.pop()\n",
    "                count +=2\n",
    "            else:\n",
    "                count += 1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        a = len(arr)\n",
    "        i = 0\n",
    "        while(i < a):\n",
    "            if arr[i] == 0 and i != a-1:\n",
    "                del arr[-1]\n",
    "                arr.insert(i+1,0)\n",
    "                i += 2\n",
    "            else:\n",
    "                i += 1           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if arr[i] == 0:\n",
    "                arr.insert(i, 0)\n",
    "                arr.pop()\n",
    "                i += 2\n",
    "            else:\n",
    "                i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        # arr = [0,0,0,0,0,0,0]\n",
    "        t_arr = []\n",
    "\n",
    "        for a in arr:\n",
    "            t_arr.append(a)\n",
    "            if len(arr) == len(t_arr):\n",
    "                break\n",
    "            if a == 0:\n",
    "                t_arr.append(a)\n",
    "                if len(arr) == len(t_arr):\n",
    "                    break\n",
    "\n",
    "        # print(t_arr)\n",
    "        # print(arr)\n",
    "        for i in range(0, len(t_arr)):\n",
    "            arr[i] = t_arr[i]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\r\n",
    "        \"\"\"\r\n",
    "        Do not return anything, modify arr in-place instead.\r\n",
    "        \"\"\"\r\n",
    "        idx = 0\r\n",
    "        len_a = len(arr)\r\n",
    "        while idx < len(arr):\r\n",
    "            if arr[idx] == 0:\r\n",
    "                arr.insert(idx, 0)\r\n",
    "                idx += 2\r\n",
    "                arr.pop()\r\n",
    "            else:\r\n",
    "                idx += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        ar = arr[:]\n",
    "        arr.clear()\n",
    "        arr.extend(list(map(int, \"\".join(map(str, ar)).replace(\"0\", \"00\")[:len(ar)])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def duplicateZeros(self, arr: List[int]) -> None:\n",
    "#        arr[:] = [x for e in arr for x in ([e] if e else [0, 0])][:len(arr)]\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        # from functools import reduce\n",
    "        # arr[:] = [x for e in arr for x in [[e] if e else [0, 0]]][:len(arr)]\n",
    "        # arr[:] = reduce(lambda x,y: x+y, arr)\n",
    "        arr[:] = sum([x for e in arr for x in [[e] if e else [0, 0]]], [])[:len(arr)]\n",
    "\n",
    "# https://stackoverflow.com/questions/952914/how-to-make-a-flat-list-out-of-list-of-lists\n",
    "# python flat用法速度排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        # 指针问题, \n",
    "        # step1 先找寻到按要求的最后一个元素位置，\n",
    "        count = 0\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            if not arr[i]:\n",
    "                count += 1\n",
    "            count += 1\n",
    "            if count >= n: break\n",
    "        \n",
    "        \n",
    "        # 双指针\n",
    "        l = i # 这就是 复写后数组的最后一处索引\n",
    "        r = n-1 # 数组末尾位置，其指针一定是不在 l 之前的\n",
    "        \n",
    "        if count > n:  # 特殊情况，如果受限于长度，最后只能复写一个0的情况\n",
    "            arr[r] = 0\n",
    "            r -= 1\n",
    "            l -= 1\n",
    "\n",
    "        while l >= 0:\n",
    "            if not arr[l]:\n",
    "                arr[r] = 0\n",
    "                arr[r-1] = 0\n",
    "                r = r - 2\n",
    "                l -= 1\n",
    "            else:\n",
    "                arr[r] = arr[l]\n",
    "                r, l = r-1, l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        idx = 0\n",
    "        while idx < n:\n",
    "            if arr[idx] == 0:\n",
    "                arr.insert(idx + 1, 0)\n",
    "                arr.pop()\n",
    "                idx += 2\n",
    "            else:\n",
    "                idx += 1\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        size = len(arr)\n",
    "        i = 0\n",
    "        while i < size:\n",
    "            if arr[i] == 0:\n",
    "                arr.insert(i, 0)\n",
    "                arr.pop()\n",
    "                i += 1\n",
    "            i += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        mark,list1 = None,[]\n",
    "        for i,num in enumerate(arr):\n",
    "            if num == 0:\n",
    "                list1 += [0,0]\n",
    "                if mark is None:\n",
    "                    mark = i\n",
    "            else:\n",
    "                list1.append(num)\n",
    "        if mark is not None:\n",
    "            for i in range(mark,len(arr)):\n",
    "                arr[i] = list1[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        list1 = []\n",
    "        mark = None\n",
    "        for i, num in enumerate(arr):\n",
    "            if num == 0:\n",
    "                list1.append(0)\n",
    "                list1.append(0)\n",
    "                mark = i if mark is None else mark\n",
    "            else:\n",
    "                list1.append(num)\n",
    "        if mark is not None:\n",
    "            for i in range(mark, len(arr)):\n",
    "                arr[i] = list1[i]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if arr[i] == 0 and i != n-1:\n",
    "                arr[:] = arr[:i+1] + [0] + arr[i+1:n-1]\n",
    "                print(len(arr))\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left < right:\n",
    "            if arr[left] == 0:\n",
    "                arr.insert(left, 0)\n",
    "                arr.pop()\n",
    "                left += 2\n",
    "            else:\n",
    "                left += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        flag = False\n",
    "        for i in range(len(arr)):\n",
    "            if flag is True:\n",
    "                flag = False\n",
    "                continue\n",
    "\n",
    "            if arr[i] == 0:\n",
    "                arr.insert(i+1, 0)\n",
    "                arr.pop()\n",
    "                flag = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        i =0 \n",
    "        while i< n:\n",
    "            if arr[i] == 0:            \n",
    "                for y in range(n-1,i,-1):\n",
    "                    arr[y]=arr[y-1]\n",
    "                if i < n-1:\n",
    "                    arr[i+1]=0\n",
    "                i+=1\n",
    "            i+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def duplicateZeros(self, arr: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        a=0\n",
    "        len_=len(arr)\n",
    "        while a<len_:\n",
    "            if arr[a]==0:\n",
    "                arr[a+1:]=arr[a:len_-1]\n",
    "                a+=2\n",
    "            else:\n",
    "                a+=1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
